% BEGIN LICENSE BLOCK
% Version: CMPL 1.1
%
% The contents of this file are subject to the Cisco-style Mozilla Public
% License Version 1.1 (the "License"); you may not use this file except
% in compliance with the License.  You may obtain a copy of the License
% at www.eclipse-clp.org/license.
% 
% Software distributed under the License is distributed on an "AS IS"
% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.  See
% the License for the specific language governing rights and limitations
% under the License. 
% 
% The Original Code is  The ECLiPSe Constraint Logic Programming System. 
% The Initial Developer of the Original Code is  Cisco Systems, Inc. 
% Portions created by the Initial Developer are
% Copyright (C) 2006 Cisco Systems, Inc.  All Rights Reserved.
% 
% Contributor(s): 
% 
% END LICENSE BLOCK

%----------------------------------------------------------------------
\chapter{The Integer Sets Library}
\label{icsets}
\index{library!ic_sets|(}
%HEVEA\cutdef[1]{section}
%----------------------------------------------------------------------


%----------------------------------------------------------------------
\section{Why Sets}
%----------------------------------------------------------------------

\index{finite sets}
The {\em ic_sets} library is a solver for constraints over the domain
of finite sets of integers.
Modelling with sets is useful for problems where one is not
interested in each item as a specific individual, but in a
collection of item where no specific distinction is made and thus
where symmetries among the element values need to be avoided.


%----------------------------------------------------------------------
\section{Finite Sets of Integers}
%----------------------------------------------------------------------

In the context of the {\em ic_sets} library, (ground) integer sets are
simply sorted, duplicate-free lists of integers e.g.
\begin{quote}\begin{verbatim}
SetOfThree = [1,3,7]
EmptySet = []
\end{verbatim}\end{quote}
Lists which contain non-integers, are unsorted or contain duplicates,
are not sets in the sense of this library.


%----------------------------------------------------------------------
\section{Set Variables}
\index{set variable}
%----------------------------------------------------------------------

%\subsection{Declaring}
Set variables are variables which can eventually take a ground integer
set as their value.  They are characterized by a lower bound (the set
of elements that are definitely in the set) and an upper bound (the
set of elements that may be in the set).  A set variable can be
declared as follows: 
\begin{quote}\begin{verbatim}
SetVar :: []..[1,2,3,4,5,6,7]
\end{verbatim}\end{quote}
%If the lower bound is the empty set (like in this case) this can be written as 
%\begin{verbatim}
%        SetVar subset [1,2,3,4,5,6,7]
%\end{verbatim}
If the lower bound is the empty set and the upper bound is a set of
consecutive integers, one can also declare it like
\begin{quote}\begin{verbatim}
intset(SetVar, 1, 7)
\end{verbatim}\end{quote}
which is equivalent to the above.    
\quickref{Declaring Set Variables}{
\begin{description}
\item[\biptxtref{?Set :: ++Lwb..++Upb}{::/2!ic_sets}{../bips/lib/ic_sets/NN-2.html}]
         Set is an integer set within the given bounds 
\item[\biptxtref{intset(?Set, +Min, +Max)}{intset/3}{../bips/lib/ic_sets/intset-3.html}]
         Set is a set containing numbers between Min and Max 
\item[\biptxtref{intsets(?Sets, ?N, +Min, +Max)}{intsets/4}{../bips/lib/ic_sets/intsets-4.html}]
         Sets is a list of N sets containing numbers between Min and Max 
\end{description}
}

The system prints set variables in a particular way, for instance:
\begin{quote}\begin{verbatim}
?- lib(ic_sets).
?- X :: [2,3]..[1,2,3,4].
X = X{[2, 3] \/ ([] .. [1, 4]) : _308{[2 .. 4]}}
\end{verbatim}\end{quote}
The curly brackets contain the description of the current domain
of the set variable in the form of
\begin{enumerate}
\item the lower bound of the set (values which definitely are in the set)
\item the union symbol \verb.\/.
\item the set of optional values (which may or may not be in the set)
\item a colon
\item a finite domain variable indicating the admissible cardinality for the set
\end{enumerate}


%----------------------------------------------------------------------
\section{Constraints}
%----------------------------------------------------------------------

\index{membership constraint}
\index{cardinality constraint}
The constraints that {\em ic_sets} implements are the usual relations
over sets.
The membership (in/2, notin/2) and cardinality constraints
(\#/2) establish
relationships between set variables and integer variables:
\quickref{Membership and Cardinality Constraints}{
\begin{description}
\item[\biptxtref{?X in ?Set}{in/2!ic_sets}{../bips/lib/ic_sets/in-2.html}]
         The integer X is member of the integer set Set 
\item[\biptxtref{?X notin ?Set}{notin/2!ic_sets}{../bips/lib/ic_sets/notin-2.html}]
         The integer X is not a member of the integer set Set 
%\item[\biptxtref{membership_booleans(?Set, ?BoolArr)}{membership_booleans/2!ic_sets}{../bips/lib/ic_sets/membership_booleans-2.html}]
%         BoolArr is an array of booleans describing Set 
\item[\biptxtref{\#(?Set, ?Card)}{\#/2!ic_sets}{../bips/lib/ic_sets/H-2.html}]
         Card is the cardinality of the integer set Set 
\end{description}
}
\begin{quote}\begin{verbatim}
?- X ::[]..[1, 2, 3], 2 in X, 3 in X, #(X, 2).
X = [2, 3]
Yes (0.01s cpu)

?- X :: []..[1, 2, 3, 4], 3 in X, 4 notin X.
X = X{[3] \/ ([] .. [1, 2]) : _2161{1 .. 3}}
Yes (0.00s cpu)
\end{verbatim}\end{quote}
Possible constraints between two sets are equality, inclusion/subset
and disjointness:
\index{inclusion constraint}
\index{disjointness constraint}
\index{subset constraint}
\begin{quote}\begin{verbatim}
?- X subset [1, 2, 3, 4].
X = X{([] .. [1, 2, 3, 4]) : _2139{0 .. 4}}
Yes (0.00s cpu)

?- X :: []..[1, 2, 3, 4], Y :: []..[3, 4, 5, 6], X subset Y.
X = X{([] .. [3, 4]) : _2176{0 .. 2}}
Y = Y{([] .. [3, 4, 5, 6]) : _2367{0 .. 4}}
There are 4 delayed goals.
Yes (0.00s cpu)

?- X :: [2] .. [1, 2, 3, 4], Y :: [3] .. [1, 2, 3, 4], X disjoint Y.
X = X{[2] \/ ([] .. [1, 4]) : _2118{1 .. 3}}
Y = Y{[3] \/ ([] .. [1, 4]) : _2213{1 .. 3}}
There are 2 delayed goals.
Yes (0.00s cpu)
\end{verbatim}\end{quote}
\quickref{Basic Set Relations}{
\begin{description}
\item[\biptxtref{?Set1 sameset ?Set2}{sameset/2!ic_sets}{../bips/lib/ic_sets/sameset-2.html}]
         The sets Set1 and Set2 are equal 
\item[\biptxtref{?Set1 disjoint ?Set2}{disjoint/2!ic_sets}{../bips/lib/ic_sets/disjoint-2.html}]
         The integer sets Set1 and Set2 are disjoint 
\item[\biptxtref{?Set1 includes ?Set2}{includes/2!ic_sets}{../bips/lib/ic_sets/includes-2.html}]
         Set1 includes (is a superset) of the integer set Set2 
\item[\biptxtref{?Set1 subset ?Set2}{subset/2!ic_sets}{../bips/lib/ic_sets/subset-2.html}]
         Set1 is a (non-strict) subset of the integer set Set2 
\item[\biptxtref{intersection(?Set1, ?Set2, ?Set3)}{intersection/3!ic_sets}{../bips/lib/ic_sets/intersection-3.html}]
         Set3 is the intersection of the integer sets Set1 and Set2 
\item[\biptxtref{union(?Set1, ?Set2, ?Set3)}{union/3!ic_sets}{../bips/lib/ic_sets/union-3.html}]
         Set3 is the union of the integer sets Set1 and Set2 
\item[\biptxtref{difference(?Set1, ?Set2, ?Set3)}{difference/3!ic_sets}{../bips/lib/ic_sets/difference-3.html}]
         Set3 is the difference of the integer sets Set1 and Set2 
\item[\biptxtref{symdiff(?Set1, ?Set2, ?Set3)}{symdiff/3!ic_sets}{../bips/lib/ic_sets/symdiff-3.html}]
         Set3 is the symmetric difference of the integer sets Set1 and Set2 
\end{description}
}
Possible constraints between three sets are for example
intersection, union, difference and symmetric difference.
For example:
\begin{quote}\begin{verbatim}
?- X :: [2, 3] .. [1, 2, 3, 4],
   Y :: [3, 4] .. [3, 4, 5, 6],
   ic_sets : intersection(X, Y, Z).
X = X{[2, 3] \/ ([] .. [1, 4]) : _2127{2 .. 4}}
Y = Y{[3, 4] \/ ([] .. [5, 6]) : _2222{2 .. 4}}
Z = Z{[3] \/ ([] .. [4]) : _2302{[1, 2]}}
There are 6 delayed goals.
Yes (0.00s cpu)
\end{verbatim}\end{quote}
\Note{Note that we needed to qualify the intersection/3 constraint with
the {\em ic_sets} module prefix because of a name conflict with a predicate from
the {\em lists} library of the same name.}
\Note{Note the lack of a complement constraint: this is because the complement
of a finite set is infinite and cannot be represented. Complements can be
modelled using an explicit universal set and a difference constraint.}

\ignore{
\subsection{Domain Access}

\begin{description}
\item[\biptxtref{potential_members(?Set, -List)}{potential_members/2}{../bips/lib/ic_sets/potential_members-2.html}]
         List is the list of elements of whose membership in Set is currently uncertain 
\item[\biptxtref{set_range(?Set, -Lwb, -Upb)}{set_range/3}{../bips/lib/ic_sets/set_range-3.html}]
         Lwb and Upb are the current lower and upper bounds on Set 
\end{description}
}

Finally, there are a number of n-ary constraints that apply to lists of sets:
disjointness, union and intersection. For example:
\quickref{N-ary Set Relations}{
\begin{description}
\item[\biptxtref{all_disjoint(+Sets)}{all_disjoint/1}{../bips/lib/ic_sets/all_disjoint-1.html}]
         Sets is a list of integers sets which are all disjoint 
\item[\biptxtref{all_union(+Sets, ?SetUnion)}{all_union/2}{../bips/lib/ic_sets/all_union-2.html}]
         SetUnion is the union of all the sets in the list Sets 
\item[\biptxtref{all_intersection(+Sets, ?SetIntersection)}{all_intersection/2}{../bips/lib/ic_sets/all_intersection-2.html}]
         SetIntersection is the intersection of all the sets in the list Sets 
\end{description}
}
\begin{quote}\begin{verbatim}
?- intsets(Sets, 5, 1, 5), all_intersection(Sets, Common).
Sets = [_2079{([] .. [1, 2, 3, 4, 5]) : _2055{0 .. 5}}, ... ]
Common = Common{([] .. [1, 2, 3, 4, 5]) : _3083{0 .. 5}}
There are 24 delayed goals.
Yes (0.00s cpu)
\end{verbatim}\end{quote}



%----------------------------------------------------------------------
%\section{Set Expressions}
%----------------------------------------------------------------------

In most positions where a set or set variable is expected one can also
use a set expression. A set expression is composed from ground sets
(integer lists), set variables, and the following set operators:
\begin{quote}\begin{verbatim}
Set1 /\ Set2       % intersection
Set1 \/ Set2       % union
Set1 \ Set2        % difference
\end{verbatim}\end{quote}
When such set expressions occur, they are translated into auxiliary
\bipref{intersection/3}{../bips/lib/ic_sets/intersection-3.html},
\bipref{union/3}{../bips/lib/ic_sets/union-3.html} and
\bipref{difference/3}{../bips/lib/ic_sets/difference-3.html}
constraints, respectively.


%----------------------------------------------------------------------
\section{Search Support}
%----------------------------------------------------------------------

The
\bipref{insetdomain/4}{../bips/lib/ic_sets/insetdomain-4.html}
predicate can be used to enumerate all ground instantiations of a set
variable, much like
\bipref{indomain/1}{../bips/lib/ic/indomain-1.html}
in the finite domain case. 
Here is an example of the default enumeration strategy:
\begin{quote}\begin{verbatim}
?-  X::[]..[1,2,3], insetdomain(X,_,_,_), writeln(X), fail.
[1, 2, 3]
[1, 2]
[1, 3]
[1]
[2, 3]
[2]
[3]
[]
\end{verbatim}\end{quote}
Other enumeration strategies can be selected (see the Reference Manual
on insetdomain/4).


%\begin{description}
%\item[\biptxtref{insetdomain(?Set, ?CardSel, ?ElemSel, ?Order)}{insetdomain/4}{../bips/lib/ic_sets/insetdomain-4.html}]
%         Instantiate Set to a possible value 
%\end{description}


%----------------------------------------------------------------------
\section{Example}
%----------------------------------------------------------------------

\index{Steiner problem}
The following program computes so-called Steiner triplets.
The problem is to compute triplets of numbers between 1 and N,
such that any two triplets have at most one element in common.
\begin{code}
:- lib(ic_sets).
:- lib(ic).

steiner(N, Sets) :-
        NB is N * (N-1) // 6,           % compute number of triplets
        intsets(Sets, NB, 1, N),        % initialise the set variables
        ( foreach(S,Sets) do
            #(S,3)                      % constrain their cardinality
        ),
        ( fromto(Sets,[S1|Ss],Ss,[]) do
            ( foreach(S2,Ss), param(S1) do
                #(S1 /\verb.\. S2, C),         % constrain the cardinality
                C #=< 1                 % of pairwise intersections
            )
        ),
        label_sets(Sets).               % search

label_sets([]).
label_sets([S|Ss]) :-
        insetdomain(S,_,_,_),
        label_sets(Ss).
\end{code}
Running this program yields the following first solution:
\begin{quote}\begin{verbatim}
?- steiner(9,X).

X = [[1, 2, 3], [1, 4, 5], [1, 6, 7], [1, 8, 9],
     [2, 4, 6], [2, 5, 8], [2, 7, 9], [3, 4, 9],
     [3, 5, 7], [3, 6, 8], [4, 7, 8], [5, 6, 9]] More? (;)
\end{verbatim}\end{quote}


%----------------------------------------------------------------------
\section{Weight Constraints}
\label{weight-constraint}
\index{weight constraint}
%----------------------------------------------------------------------

\index{knapsack}
\index{bin packing}
Another constraint between sets and integers is the weight/3 constraint.
It allows the association of weights to set elements, and can help when
solving problems of the knapsack or bin packing type.
The constraint takes a set and an array of element weights and
constrains the weight of the whole set:
\begin{quote}\begin{verbatim}
?- ic_sets:(Container :: [] .. [1, 2, 3, 4, 5]),
   Weights = [](20, 34, 9, 12, 19),
   weight(Container, Weights, W).
Container = Container{([] .. [1, 2, 3, 4, 5]) : _2127{0 .. 5}}
Weights = [](20, 34, 9, 12, 19)
W = W{0 .. 94}
There is 1 delayed goal.
Yes (0.01s cpu)
\end{verbatim}\end{quote}
By adding a capacity limit and a search primitive, we can solve a
knapsack problem:
\begin{quote}\begin{verbatim}
?- ic_sets:(Container :: [] .. [1, 2, 3, 4, 5]),
   Weights = [](20, 34, 9, 12, 19),
   weight(Container, Weights, W),
   W #=< 50,
   insetdomain(Container,_,_,_).
Weights = [](20, 34, 9, 12, 19)
W = 41
Container = [1, 3, 4]
More (0.00s cpu)
\end{verbatim}\end{quote}

By using the heuristic options provided by insetdomain, we can
implement a greedy heuristic, which finds the optimal solution
(in terms of greatest weight) straight away:
\index{greedy heuristic}
\begin{quote}\begin{verbatim}
?- ic_sets:(Container :: [] .. [1, 2, 3, 4, 5]),
   Weights = [](20, 34, 9, 12, 19),
   weight(Container, Weights, W),
   W #=< 50,
   insetdomain(Container,decreasing,heavy_first(Weights),_).
W = 48
Container = [1, 3, 5]
Weights = [](20, 34, 9, 12, 19)
More (0.00s cpu)
\end{verbatim}\end{quote}
\quickref{Set Weight Constraint}{
\begin{description}
\item[\biptxtref{weight(?Set, ++ElementWeights, ?Weight)}{weight/3}{../bips/lib/ic_sets/weight-3.html}]
         According to the array of element weights, the weight of set Set1 is Weight 
\end{description}
}


\section{Exercises}

\begin{enumerate}

\item

Consider the knapsack problem in section~\ref{weight-constraint}.
Suppose that the items each have an associated profit, namely 17, 38, 18, 10
and 5, respectively.  Which items should be included to maximise profit?


\item

Write a predicate which, given a list of sizes of items and a list of
capacities of buckets, returns a list of (ground) sets indicating which
items should go into each bucket.  Obviously each item should go into
exactly one bucket.

Try it out with 5 items of sizes 20, 34, 9, 12 and 19, into 3 buckets of
sizes 60, 20 and 20.

\end{enumerate}

\index{library!ic_sets|)}

%HEVEA\cutend
